﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FisheryPlatform.Search.Core.Analysis
{
    /// <summary>
    /// Complex Maximum Matching function (Chen & Liu, 1992) and four disambiguation rules
    /// Priority of ambiguity resolution rules:
    ///      1. Maximum Matching
    ///      2. Largest Average Word Length
    ///      3. Smallest Variance of Word Lengths
    ///      4. Largest Sum of 100xlog(charfreq)
    /// </summary>
    /// <author>gwd, 2006-5-26</author>
    public class MMWordIdentifier : WordIdentifier
    {
        private const double DELTA = 10e-6;

        #region class WordChunk

        /*
    * WordChunk is the chunk that holds the 3 temp words to analysis, and the
    * WordChunk is just a exploring tree. The first level wordChunk is just a
    * container, it does not contain any useful word, then the level 1, 2, 3
    * contain the exact words
    */
        protected internal class WordChunk
        {
            public string Word;
            public int Level;
            public int Offset;
            public WordChunk Father;
            public System.Collections.ArrayList Children = new System.Collections.ArrayList();

            public WordChunk()
            {
                Word = "";
                Level = 0;
                Offset = 0;
                Father = null;
            }

            public WordChunk(WordChunk father)
            {
                Word = "";
                Level = father.Level + 1;
                Offset = father.Offset + father.Word.Length;
                father.Children.Add(this);
                Father = father;
            }

            public override string ToString()
            {
                string s = "";
                if (this.Father != null) s = "Father=(" + this.Father.ToString() + "), ";
                s += "Word=" + this.Word + ", ";
                s += "Level=" + this.Level + ", ";
                s += "Offset=" + this.Offset;

                return s;
            }

        }

        #endregion class WordChunk

        private System.Collections.ArrayList _chunkLeaves = new System.Collections.ArrayList();

        public MMWordIdentifier(Dictionary dic)
            : base(dic)
        { }

        /// <summary>
        /// Identify words from "content".
        /// </summary>
        /// <param name="content"></param>
        /// <returns></returns>
        public override string[] IdentifyWord(string content)
        {
            _chunkLeaves.Clear();
            string buffer = content;
            System.Collections.Specialized.StringCollection result = new System.Collections.Specialized.StringCollection();

            WordChunk chunk = new WordChunk();
            int index = 0;
            while (true)
            {
                GetWordChunk(buffer, chunk);
                WordChunk[] chunks = FilterLongestChunk();
                if (chunks.Length == 0)
                {
                    System.Console.Out.WriteLine("Error: Did not find any chunks");
                }
                else
                {
                    WordChunk state = chunks[0];
                    // apply other three disambiguation rules, if needed.
                    chunks = FilterAverageWordLength(chunks);
                    chunks = FilterVarianceWordLength(chunks);
                    chunks = FilterMophemicDegree(chunks);

                    WordChunk fstChunk;
                    if (chunks == null || chunks.Length == 0)
                    {
                        fstChunk = state;
                    }
                    else
                        fstChunk = chunks[chunks.Length - 1]; // ##
                    while (fstChunk.Father.Level != 0)
                    {
                        fstChunk = fstChunk.Father;
                    }
                    string word = fstChunk.Word;
                    result.Add(word);

                    index += word.Length;
                    if (index >= content.Length) break;

                    buffer = content.Substring(index);
                }
                _chunkLeaves.Clear();
                chunk = new WordChunk();
            }

            string[] retValue = new string[result.Count];
            result.CopyTo(retValue, 0);
            return retValue;
        }

        #region four disambiguation rules

        /// <summary>
        /// Maximum Matching
        /// </summary>
        /// <returns></returns>
        protected internal virtual WordChunk[] FilterLongestChunk()
        {
            //DateTime start = DateTime.Now;

            WordChunk[] result = null;
            System.Collections.ArrayList chunks = new System.Collections.ArrayList();

            // Find the longest size;
            int max = 0;
            int length = _chunkLeaves.Count;
            for (int i = 0; i < length; i++)
            {
                WordChunk chunk = (WordChunk)_chunkLeaves[i];
                int size = chunk.Offset + chunk.Word.Length;
                if (size > max)
                    max = size;
            }

            for (int i = 0; i < length; i++)
            {
                WordChunk chunk = (WordChunk)_chunkLeaves[i];
                if (chunk.Offset + chunk.Word.Length == max)
                    chunks.Add(chunk);
            }

            result = new WordChunk[chunks.Count];
            chunks.CopyTo(result);
            //MMSupport.Debug(string.Format("FilterLongestChunk: {0}", (DateTime.Now - start).TotalMilliseconds));
            return result;
        }

        /// <summary>
        /// Largest Average Word Length
        /// </summary>
        /// <param name="chunks"></param>
        /// <returns></returns>
        protected internal virtual WordChunk[] FilterAverageWordLength(WordChunk[] chunks)
        {
            if (chunks.Length == 1)
                return chunks;

            //DateTime start = DateTime.Now;

            WordChunk[] result = null;
            System.Collections.ArrayList resList = new System.Collections.ArrayList();

            double max = 0;
            for (int i = 0; i < chunks.Length; ++i)
            {
                int size = chunks[i].Offset + chunks[i].Word.Length;
                double avgLength = (double)(((double)size) / (double)(chunks[i].Level));
                if (max < avgLength)
                    max = avgLength;
            }

            for (int i = 0; i < chunks.Length; ++i)
            {
                int size = chunks[i].Offset + chunks[i].Word.Length;
                double avgLength = (double)(((double)size) / (double)(chunks[i].Level));
                if (System.Math.Abs(max - avgLength) <= DELTA)
                    resList.Add(chunks[i]);
            }

            result = new WordChunk[resList.Count];
            resList.CopyTo(result);
            //MMSupport.Debug(string.Format("FilterAverageWordLength: {0}", (DateTime.Now - start).TotalMilliseconds));
            return result;
        }

        /// <summary>
        /// Smallest Variance of Word Lengths
        /// </summary>
        /// <param name="chunks"></param>
        /// <returns></returns>
        protected internal virtual WordChunk[] FilterVarianceWordLength(WordChunk[] chunks)
        {
            if (chunks.Length == 1)
                return chunks;

            //DateTime start = DateTime.Now;

            WordChunk[] result = null;
            System.Collections.ArrayList resList = new System.Collections.ArrayList();

            double min = 9999;
            for (int i = 0; i < chunks.Length; ++i)
            {
                int size = chunks[i].Offset + chunks[i].Word.Length;
                double avgLength = (double)(((double)size) / (double)(chunks[i].Level));
                double varLength = ComputeVarianceWordLength(chunks[i], avgLength);
                if (min > varLength)
                    min = varLength;
            }

            for (int i = 0; i < chunks.Length; ++i)
            {
                int size = chunks[i].Offset + chunks[i].Word.Length;
                double avgLength = (double)(((double)size) / (double)(chunks[i].Level));
                double varLength = ComputeVarianceWordLength(chunks[i], avgLength);
                if (System.Math.Abs(min - varLength) <= DELTA)
                    resList.Add(chunks[i]);
            }

            result = new WordChunk[resList.Count];
            resList.CopyTo(result);
            //MMSupport.Debug(string.Format("FilterVarianceWordLength: {0}", (DateTime.Now - start).TotalMilliseconds));
            return result;
        }

        protected internal virtual double ComputeVarianceWordLength(WordChunk chunk, double avgLength)
        {
            double varLength = 0;
            WordChunk node = chunk;
            while (node.Level != 0)
            {
                varLength += (node.Word.Length - avgLength) * (node.Word.Length - avgLength);
                node = node.Father;
            }
            return varLength;
        }

        /// <summary>
        /// Largest Sum of 100xlog(charfreq)
        /// </summary>
        /// <param name="chunks"></param>
        /// <returns></returns>
        protected internal virtual WordChunk[] FilterMophemicDegree(WordChunk[] chunks)
        {
            if (chunks.Length == 1)
                return chunks;

            //DateTime start = DateTime.Now;

            WordChunk[] result = null;
            System.Collections.ArrayList resList = new System.Collections.ArrayList();

            double max = 0;
            for (int i = 0; i < chunks.Length; ++i)
            {
                double mphDegreeSum = ComputeMorphemicDegreeSum(chunks[i]);
                if (max < mphDegreeSum)
                    max = mphDegreeSum;
            }

            for (int i = 0; i < chunks.Length; ++i)
            {
                double mphDegreeSum = ComputeMorphemicDegreeSum(chunks[i]);
                if (System.Math.Abs(max - mphDegreeSum) <= DELTA)
                    resList.Add(chunks[i]);
            }

            result = new WordChunk[resList.Count];
            resList.CopyTo(result);
            //MMSupport.Debug(string.Format("FilterMophemicDegree: {0}", (DateTime.Now - start).TotalMilliseconds));
            return result;
        }

        protected internal virtual double ComputeMorphemicDegreeSum(WordChunk chunk)
        {
            double morDegreeSum = 0;
            WordChunk node = chunk;
            while (node.Level != 0)
            {
                if (node.Word.Length == 1)
                {
                    morDegreeSum += System.Math.Log(_dictionary.GetCharacterFreq(node.Word));
                }
                node = node.Father;
            }
            return morDegreeSum;
        }

        #endregion

        /// <summary>
        /// Another implement of GetWordChunk.
        /// </summary>
        /// <param name="content"></param>
        /// <param name="chunk"></param>
        protected internal virtual void GetWordChunk_v1(string content, WordChunk chunk)
        {
            if (content.Trim().Equals("")) return;

            if (content.Length == 1)
            {
                WordChunk newChunk = new WordChunk(chunk);
                newChunk.Word = content;
                _chunkLeaves.Add(newChunk);
                return;
            }

            int maxWordLength;
            string word = "";
            string buffer = "";

            #region Level1 WordChunk
            buffer = content;
            maxWordLength = buffer.Length >= _dictionary.MaxWordLength ? _dictionary.MaxWordLength : buffer.Length;
            WordChunk chunk1 = new WordChunk(chunk);
            chunk1.Word = buffer.Substring(0, 1);
            for (int i = 2; i <= maxWordLength; i++)
            {
                word = buffer.Substring(0, i);
                if (_dictionary.Lookup(word))
                {
                    WordChunk newChunk1 = new WordChunk(chunk);
                    newChunk1.Word = word;
                }
            }
            #endregion

            #region Level2 WordChunk
            for (int j = chunk.Children.Count - 1; j >= 0; j--)
            {
                WordChunk aChunk1 = (WordChunk)chunk.Children[j];
                // reach to the end of the content already.
                if (aChunk1.Offset + aChunk1.Word.Length >= content.Length)
                {
                    _chunkLeaves.Add(aChunk1);
                    chunk.Children.Remove(aChunk1);
                    continue;
                }

                WordChunk chunk2 = new WordChunk(aChunk1);
                buffer = content.Substring(chunk2.Offset);
                chunk2.Word = buffer.Substring(0, 1);
                if (chunk2.Offset + 1 >= content.Length)
                {
                    _chunkLeaves.Add(chunk2);
                    aChunk1.Children.Remove(chunk2);
                    continue;
                }
                maxWordLength = buffer.Length >= _dictionary.MaxWordLength ? _dictionary.MaxWordLength : buffer.Length;
                for (int i = 2; i <= maxWordLength; i++)
                {
                    word = buffer.Substring(0, i);
                    if (_dictionary.Lookup(word))
                    {
                        WordChunk newChunk2 = new WordChunk(aChunk1);
                        newChunk2.Word = word;
                    }
                }
            }
            #endregion

            #region Level3 WordChunk
            for (int k = 0; k < chunk.Children.Count; k++)
            {
                WordChunk aChunk1 = (WordChunk)chunk.Children[k];
                for (int j = 0; j < aChunk1.Children.Count; j++)
                {
                    WordChunk aChunk2 = (WordChunk)aChunk1.Children[j];
                    // reach to the end of the content already.
                    if (aChunk2.Offset + aChunk2.Word.Length >= content.Length)
                    {
                        _chunkLeaves.Add(aChunk2);
                        continue;
                    }

                    WordChunk chunk3 = new WordChunk(aChunk2);
                    buffer = content.Substring(chunk3.Offset);
                    chunk3.Word = buffer.Substring(0, 1);
                    _chunkLeaves.Add(chunk3);
                    maxWordLength = buffer.Length >= _dictionary.MaxWordLength ? _dictionary.MaxWordLength : buffer.Length;
                    for (int i = 2; i <= maxWordLength; i++)
                    {
                        word = buffer.Substring(0, i);
                        if (_dictionary.Lookup(word))
                        {
                            WordChunk newChunk3 = new WordChunk(aChunk2);
                            newChunk3.Word = word;

                            _chunkLeaves.Add(newChunk3);
                        }
                    }
                }
            }
            #endregion

            //      MMSupport.Debug(content);
            //      for (int i=0; i<_chunkLeaves.Count; i++)
            //        MMSupport.Debug(i + ": " + _chunkLeaves[i].ToString());
            //      MMSupport.Debug("");
        }

        /// <summary>
        /// Get the three-words chunk.
        /// </summary>
        /// <param name="content"></param>
        /// <param name="chunk"></param>
        protected internal virtual void GetWordChunk(string content, WordChunk chunk)
        {
            if (content.Trim().Equals("")) return;

            if (content.Length == 1)
            {
                WordChunk newChunk = new WordChunk(chunk);
                newChunk.Word = content;
                _chunkLeaves.Add(newChunk);
                return;
            }

            int maxWordLength;
            string word = "";

            maxWordLength = content.Length >= _dictionary.MaxWordLength ? _dictionary.MaxWordLength : content.Length;
            WordChunk chunk1 = new WordChunk(chunk);
            chunk1.Word = content.Substring(0, 1);
            if (chunk1.Level == 3)
                _chunkLeaves.Add(chunk1);
            else
                GetWordChunk(content.Substring(1), chunk1);
            for (int i = 2; i <= maxWordLength; i++)
            {
                word = content.Substring(0, i);
                if (_dictionary.Lookup(word))
                {
                    WordChunk newChunk1 = new WordChunk(chunk);
                    newChunk1.Word = word;

                    if (newChunk1.Level < 3)
                    {
                        // this is the real condition: if(newChunk1.Offset+newChunk1.Word.Length >= chunk.offset+chunk.Word.Length+content.Length)
                        // and newChunk1.Offset = chunk.offset+chunk.Word.Length;
                        if (newChunk1.Word.Length >= content.Length)
                        {
                            _chunkLeaves.Add(newChunk1);
                            continue;
                        }
                        GetWordChunk(content.Substring(word.Length), newChunk1);
                    }
                    else
                        _chunkLeaves.Add(newChunk1);
                }
            }

            //      if (chunk.Level == 0)
            //      {
            //        MMSupport.Debug(content);
            //        for (int i=0; i<_chunkLeaves.Count; i++)
            //          MMSupport.Debug(i + ": " + _chunkLeaves[i].ToString());
            //        MMSupport.Debug("");
            //      }
        }

    }
}
